jupytext:
formats: md:myst
text_representation:
extension: .md
format_name: myst
format_version: 0.13
jupytext_version: 1.11.5
kernelspec:
display_name: Python 3
language: python
name: python3
We begin our systematic study of the set of integers , and its properties. This is the part of mathematics called number theory and we will give an introduction to this field of mathematics
One important property of integers is that they are ordered. We can talk about one integer being greater than another integer
bdg-warningRecall , the set of positive integers
" " has some important properties
Another way to look at "" is geometrically using a number line
import matplotlib.pyplot as plt
import matplotlib.ticker as ticker
# Setup a plot such that only the bottom spine is shown
def setup(ax):
ax.spines['right'].set_color('none')
ax.spines['left'].set_color('none')
ax.spines['top'].set_color('none')
ax.yaxis.set_major_locator(ticker.NullLocator())
ax.xaxis.set_ticks_position('bottom')
ax.tick_params(which='major', width=1.00)
ax.set_xlim(-5, 5)
plt.figure(figsize=(10, 5))
n = 8
ax = plt.subplot(n, 1, 2)
setup(ax)
ax.xaxis.set_major_locator(ticker.MultipleLocator(1))
ax.set_xlabel("Number Line, ℤ")
ax.text(-5, 1, "$\cdots\ -n\ \ \cdots$", fontsize=14, ha='center', va='center')
ax.text(5, 1, "$\cdots\ n\ \cdots$", fontsize=14, ha='center', va='center')
# Add arrow ends to the x-axis
arrowprops = dict(arrowstyle='<|-|>', linewidth=2.5, color='black')
ax.annotate('', xy=(-4, 1), xytext=(4, 1), arrowprops=arrowprops)
plt.show()
Then iff is not to the right of ,
for example for being then
" " is an example of mathematical object called a linear or total order
If we change property Anti-Symmetry and keep the Reflexive and Transitive we get another type of mathematical object called an equivalence relation
Well Ordered Property W.O.P.
: Every non-empty subset that is bounded below has a least member
# Setup a plot such that only the bottom spine is shown
def setup(ax):
ax.spines['right'].set_color('none')
ax.spines['left'].set_color('none')
ax.spines['top'].set_color('none')
ax.yaxis.set_major_locator(ticker.NullLocator())
ax.set_xlim(-5, 5)
ax.xaxis.set_major_locator(ticker.NullLocator())
ax.xaxis.set_minor_locator(ticker.NullLocator())
plt.figure(figsize=(10, 5))
n = 8
ax = plt.subplot(n, 1, 2)
setup(ax)
ax.set_xlabel("Number Line, ℤ")
# Add arrow ends to the x-axis
arrowprops = dict(arrowstyle='-|>', linewidth=1, color='black')
ax.annotate('k', xy=(-4, 0), xytext=(-4, 1), arrowprops=arrowprops)
ax.annotate('x - smallest element in $\mathrm{S}$', xy=(-3, 0), xytext=(-3, 2), arrowprops=arrowprops)
ax.text(-1, 0.5, "The Set $\mathrm{S}$", color="white", ha="center", va="center", weight="bold")
plt.fill("j", "k", "0.7",
data={"j": [-3, -3, 1, 1],
"k": [0, 1, 1, 0]})
plt.show()
This property is important because it allows us to prove the principle of mathematical induction among other important result
The rational number do not obey the W.O.P. and this in part motivates the construction of the real numbers as the following example shows
The first concept we will deal with is division of integers we examine when
Let $a, a\ne 0, b, c\in\Bbb{Z}$\
If $a\mid b$ and $a\mid c$ then\
$a\mid (mb+nc)$ $\forall m,n\in\Bbb{Z}$
You can use first two statements of *Theorem 1*
> If a divides b and c then a divides a linear combination of those numbers
Let $p\in\Bbb{Z},\ p\ge 2$\
We call $p$ a **prime integer** or just **p is prime** if the only *positive* factors of $p$ are $1$ and $p$
If $p\ge 2$ is not a prime it is called a **composite**
Note
is composite iff such that and
is not a prime number by definition
:class: dropdown
$17, 53$ are prime
$52, 99$ are composite\
{bdg-primary}`Note` $99=9\cdot 11=3\cdot 3\cdot 11=3^2\cdot 11$\
We call $3^2\cdot 11$ the **prime factorization** of $99$
That there is only one way to factor a composite number as a product of primes is the following result There is only one prime factorization for a composite number
Theorem 2 The Fundamental Theorem Of Arithmetic
bdg-primaryNote is the same prime factorization of as
$205=5\cdot 41$ and $41$ is prime\
$206=2\cdot 103$ is 103 prime?
We can check to see if $103$ is prime by dividing $103$ by all the numbers from $2$ to $\lceil\frac{103}{2}\rceil =52$. {bdg-danger}`Problem` Thats a lot of checking
Faster way to check Primality Theorem 3
bdg-secondaryProof
If is composite, such that , so for some
We claim or
If, not then
Thus has a divisor , say ""
If this divisor is not prime, it will have a prime factor , and for some , and
To show if $103$ is prime or composite we now only have to divide by all primes $\le\sqrt{103}$, ie by $2,3,5,7$ since $\lfloor\sqrt{103}\rfloor=10$ **But none of them work**
$\frac{103}{2}\notin\Bbb{Z},\frac{103}{3}\notin\Bbb{Z},\frac{103}{5}\notin\Bbb{Z},\frac{103}{7}\notin\Bbb{Z}$
Thus $103$ is prime
The method of determining primality or primality test is dependent on having a list of prime numbers up to the square root of the number to be tested
We can get this list using the Sieve of Erathosthenes
Suppose we want to find all the prime numbers less than a certain number say
We write a list of the first one hundred numbers. We exclude since it is not a prime. We then circle the number 2, and cross off every second number after, ie cross cross all multiples of 2. We now circle the first uncrossed number which is 3, it is prime. We now cross off every third number, the multiples of 3. We now circle the next uncrossed off number, 5, it is prime, and we cross off all multiples of 5. We now circle the next uncrossed off number, 7 it is a prime, and cross off all multiples of 7.
In view of Theorem 3, every uncrossed off number is prime.
In fact if we have a list up to 120, these 4 iterations of the algorithm will give all primes less then 120, by Theorem 3
Theorem 4 Euclid
bdg-secondaryProof
Assume that there are a finite number of primes
bdg-infoConsider
There are two possibilities for ; composite or prime
If is prime, then the list is not complete
If is composite, by the Fundamental Theorem of Arithmetic we can write , where are on the list
Then by then 1 ie , not possible
Thus the list is not complete for any
Hence there are an infinite number of prime numbers
While the list of prime numbers will never be complete, the search for the largest known primes number is very active.
For about the last 300 years the largest known prime number has been a special type of number called Mersenne Prime
a prime number of the form $2^P-1, P\text{ is a prime number}$ is called a **Mersenne Prime**Theorem 5 The Division Algorithm
Let , Then unique numbers such that
bdg-infoNotation
Here we call
the dividend
the divisor
the quotient
the remainder
as a short hand we can also write
Another Way we can express these concepts is as below
div , and mod
$37 = 4\cdot 9 + 1$\
$39 = 4\cdot 9 + 3$\
$-39 = 4(-10) + 1$\
{bdg-danger}`Remember` not $-39 = 4(-9) -3$ since the **remainder must be non-negative**
bdg-secondaryProof
Let
The set is non empty since iff and clearly we can take negative enough so,
Clearly is bounded below by and hence it has a least element for some
We only need to show to complete the proof
Suppose not : ie suppose r and is the least element of
Let
Thus and - since and hence is not the least element of , a contradiction
Thus and
Let , ie,
Greatest Common DivisorThe largest integer $d$ that divides both $a$ and $b$ is the **Greatest Common Divisor** and we write $d=gcd(a,b)$
The will exist because there are only a finite number of divisors of and and the lists for both and of divisors contain the number
badge-warningExample Find the
The prime factorization of
The prime factorization of
Clearly
Note
When is the only number on both lists of divisors of and , we say that they are relatively prime
bdg-successDefinitions
eg The prime factorizations of and gives us a means to find and write down the
a &= p_{1}^{n_1}\cdot p_{2}^{n_2}\cdot p_{3}^{n_3}\cdot \cdots p_{t}^{n_t}\cdot\ ,\ n_i\ge 0\\ b &= p_{1}^{m_1}\cdot p_{2}^{m_2}\cdot p_{3}^{m_3}\cdot \cdots p_{t}^{m_t}\cdot\ ,\ m_i\ge 0Then
where
This of course assumes that we the prime factorizations of and
This can be a difficulty when finding the
Least Common MultipleLet $a,b\in\Bbb{Z}^+$ The least Common multiple $a$, $b$ is the samllest number, $l$, divisible by both $a$ and $b$ and we write $l=lcm(a,b)$
The exists because the set of the set of multiples and is a non-empty set of integers bounded below. By the Well Ordered Property it has a least element
With the notation above, we can calculate
Theorem 6
To calculate and hence by eqth6 we don't have to find the prime factorization of We can use the Euclidean Algorithm, essentially a repeated application of the Division Algorithm to find . This method is also used to find in the following theorem
Theorem 7
Let then such that
bdg-secondaryProof
Let
is non-empty, take , , then
By the Well Ordered Principle, has a least element , for some
We now show two things
If and then (Theorem One) so,
Thus for some
Note
and in the theorem are not unique since
A use for the
Suppose we want to add two fractions to do this we find the lowest common denominator which is
Thus the easiest way to add
instead of blindly using as the common denominator,
In algebra this is useful as in the following example
Consider the question:
A computer program takes 117 hours to run. It is started at 4pm. What time if day will it be complete?
Since we are only considering the time of day and not the actual day, we must convert hours into days and hours and add the number if hours to 4pm
bdg-successSolution we then add 21 hours to 4pm to get 1pm
What we have done in the above calculation is since we are only concerned with the 24 hours in a day and not the number of days involved
If and are integers and is a positive integer, then is congruent to be modulo if divides
bdg-Info
Notationiff
That is , have the same remainder when divided by
then iff or
Or in words and have the same remainder when divided using the division algorithm
Examples
Is congruent to
Yes because which is divisible by
Is and are congruent modulo
No because which is not divisible by
Let $m$ be a positive integer. The integers $a$ and $b$ are congruent modulo $m$ if and only if there is an integer $k$ such that $a=b+km$
Attention
Some properties that may be obvious if you think about it
The set of all integers congruent to an integer a modulo m is called the congruence class of a modulo m and treat the union of these equivalence classes is the set of integers
:label: modtheory
Let $m\ge 2$, $m\in\Bbb{Z}$\
If $a\equiv b\pmod m$ and $c\equiv d\pmod m$\
then $a+b\equiv b + d\pmod m$ and $a\cdot b\equiv b\cdot d\pmod m$
If we take congruences modulo of it splits into distinct congruent classes
bdg-secondaryExample Let
An application of modular arithmetic
Randomly chosen numbers are often needed for computer simulations. Because the numbers used are generated by systematic methods they are not truly random and so are called pseudo-random numbers
A commonly used procedure is called the linear congruential method
Choose four integers:
m\ &=\ modulus &2\le\ &a& \lt m\\ a\ &=\ multiplier &0\le\ &c& \lt m\\ c\ &=\ increment\ \ &0\le\ &x_0& \lt m\\ x_0\ &=\ seed\\We use these numbers to generate a sequence of pseudo-random numbers with , by using the recursive definition
Many computer experiments need pseudo-random numbers between 0 and 1
To get these take
Let us consider the following examples
Then
x_0 &= 3\\ x_1 &= 7\cdot 3 + 4 &= 25& \equiv 7 \pmod 9\\ x_2 &= 7\cdot 7 + 4 &= 53& \equiv 8 \pmod 9\\ x_3 &= 7\cdot 8 + 4 &= 60& \equiv 6 \pmod 9\\ x_4 &= 7\cdot 6 + 4 &= 46& \equiv 1 \pmod 9\\ x_5 &= 7\cdot 1 + 4 &= 11& \equiv 2 \pmod 9\\ x_6 &= 7\cdot 2 + 4 &= 18& \equiv 0 \pmod 9\\ x_7 &= 7\cdot 0 + 4 &=\ 4& \equiv 4 \pmod 9\\ x_8 &= 7\cdot 4 + 4 &= 32& \equiv 5 \pmod 9\\ x_9 &= 7\cdot 5 + 4 &= 39& \equiv 3 \pmod 9\\Since , and the next term depends on only the previous term, the sequence repeats after 9 different outputs this generator thus gives the sequence
The sequence generated need not be of length before repetition occurs
Consider , ,
Then and
x_0 &= 1\\ x_1 &= 4\\ x_2 &= 3\cdot 4 + 1 &= 13& \equiv 3 \pmod {10}\\ x_3 &= 3\cdot 3 + 1 &= 10& \equiv 0 \pmod {10}\\ x_4 &= 3\cdot 0 + 1 &= 1\ & = 1\\Thus we get the sequence
However, conditions can be put on so that the resulting sequence has a very long period
For example, a widely used generator, has
,
This pure-multiplicative generator (called so because ) generates a sequence numbers long before repetition for any seed, x0,
Note
is a prime number as was shown by Euler in 1750 (not published until 1772) and
Of Modular Arithmetic
Let Then iff divides the sum of the digits of its decimal representation as well, iff divides the sum of the digits of its decimal representation
This is so because and
Now if and only if repeated application of following prf:refmodtheory gives